关于二叉树的22个常见问题

2024-07-16 23:14| 来源: 网络整理| 查看: 265

先上二叉树的数据结构：

class TreeNode{ int val; //左孩子 TreeNode left; //右孩子 TreeNode right; }

二叉树的题目普遍可以用递归和迭代的方式来解

1. 求二叉树的最大深度

int maxDeath(TreeNode node){ if(node==null){ return 0; } int left = maxDeath(node.left); int right = maxDeath(node.right); return Math.max(left,right) + 1; }

2. 求二叉树的最小深度

int getMinDepth(TreeNode root){ if(root == null){ return 0; } return getMin(root); } int getMin(TreeNode root){ if(root == null){ return Integer.MAX_VALUE; } if(root.left == null&&root.right == null){ return 1; } return Math.min(getMin(root.left),getMin(root.right)) + 1; }

3. 求二叉树中节点的个数

int numOfTreeNode(TreeNode root){ if(root == null){ return 0; } int left = numOfTreeNode(root.left); int right = numOfTreeNode(root.right); return left + right + 1; }

4. 求二叉树中叶子节点的个数

int numsOfNoChildNode(TreeNode root){ if(root == null){ return 0; } if(root.left==null&&root.right==null){ return 1; } return numsOfNodeTreeNode(root.left)+numsOfNodeTreeNode(root.right); }

5. 求二叉树中第k层节点的个数

int numsOfkLevelTreeNode(TreeNode root,int k){ if(root == null||k1){ return -1; } return Math.max(left, right) + 1; }

7.判断二叉树是否是完全二叉树

什么是完全二叉树呢？参见

boolean isCompleteTreeNode(TreeNode root){ if(root == null){ return false; } Queue queue = new LinkedList(); queue.add(root); boolean result = true; boolean hasNoChild = false; while(!queue.isEmpty()){ TreeNode current = queue.remove(); if(hasNoChild){ if(current.left!=null||current.right!=null){ result = false; break; } }else{ if(current.left!=null&¤t.right!=null){ queue.add(current.left); queue.add(current.right); }else if(current.left!=null&¤t.right==null){ queue.add(current.left); hasNoChild = true; }else if(current.left==null&¤t.right!=null){ result = false; break; }else{ hasNoChild = true; } } } return result; }

8. 两个二叉树是否完全相同

boolean isSameTreeNode(TreeNode t1,TreeNode t2){ if(t1==null&&t2==null){ return true; } else if(t1==null||t2==null){ return false; } if(t1.val != t2.val){ return false; } boolean left = isSameTreeNode(t1.left,t2.left); boolean right = isSameTreeNode(t1.right,t2.right); return left&&right; }

9. 两个二叉树是否互为镜像

boolean isMirror(TreeNode t1,TreeNode t2){ if(t1==null&&t2==null){ return true; } if(t1==null||t2==null){ return false; } if(t1.val != t2.val){ return false; } return isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left); }

10. 翻转二叉树or镜像二叉树

TreeNode mirrorTreeNode(TreeNode root){ if(root == null){ return null; } TreeNode left = mirrorTreeNode(root.left); TreeNode right = mirrorTreeNode(root.right); root.left = right; root.right = left; return root; }

11. 求两个二叉树的最低公共祖先节点

TreeNode getLastCommonParent(TreeNode root,TreeNode t1,TreeNode t2){ if(findNode(root.left,t1)){ if(findNode(root.right,t2)){ return root; }else{ return getLastCommonParent(root.left,t1,t2); } }else{ if(findNode(root.left,t2)){ return root; }else{ return getLastCommonParent(root.right,t1,t2) } } } // 查找节点node是否在当前二叉树中 boolean findNode(TreeNode root,TreeNode node){ if(root == null || node == null){ return false; } if(root == node){ return true; } boolean found = findNode(root.left,node); if(!found){ found = findNode(root.right,node); } return found; }

12. 二叉树的前序遍历

迭代解法

ArrayList preOrder(TreeNode root){ Stack stack = new Stack(); ArrayList list = new ArrayList(); if(root == null){ return list; } stack.push(root); while(!stack.empty()){ TreeNode node = stack.pop(); list.add(node.val); if(node.right!=null){ stack.push(node.right); } if(node.left != null){ stack.push(node.left); } } return list; }

递归解法

ArrayList preOrderReverse(TreeNode root){ ArrayList result = new ArrayList(); preOrder2(root,result); return result; } void preOrder2(TreeNode root,ArrayList result){ if(root == null){ return; } result.add(root.val); preOrder2(root.left,result); preOrder2(root.right,result); }

13. 二叉树的中序遍历

ArrayList inOrder(TreeNode root){ ArrayList list = new ArrayListinend){ return null; } TreeNode root = new TreeNode(preorder[prestart]); int position = findPosition(inorder,instart,inend,preorder[start]); root.left = myBuildTree(inorder,instart,position-1,preorder,prestart+1,prestart+position-instart); root.right = myBuildTree(inorder,position+1,inend,preorder,position-inend+preend+1,preend); return root; } int findPosition(int[] arr,int start,int end,int key){ int i; for(i = start;inode.val){ tmp = tmp.left; }else{ tmp = tmp.right; } } if(last!=null){ if(last.val>node.val){ last.left = node; }else{ last.right = node; } } return root; }

17.输入一个二叉树和一个整数，打印出二叉树中节点值的和等于输入整数所有的路径

void findPath(TreeNode r,int i){ if(root == null){ return; } Stack stack = new Stack(); int currentSum = 0; findPath(r, i, stack, currentSum); } void findPath(TreeNode r,int i,Stack stack,int currentSum){ currentSum+=r.val; stack.push(r.val); if(r.left==null&&r.right==null){ if(currentSum==i){ for(int path:stack){ System.out.println(path); } } } if(r.left!=null){ findPath(r.left, i, stack, currentSum); } if(r.right!=null){ findPath(r.right, i, stack, currentSum); } stack.pop(); }

18.二叉树的搜索区间

给定两个值 k1 和 k2（k1 < k2）和一个二叉查找树的根节点。找到树中所有值在 k1 到 k2 范围内的节点。即打印所有x (k1 =k1&&root.val

【本文地址】

公司简介

联系我们